1. Field of the Invention
This invention relates to elliptic curve cryptography and more particularly to reduction operations associated with elliptic curve operations.
2. Description of the Related Art
Elliptic Curve Cryptography (ECC) is evolving as an attractive alternative to other public-key schemes such as RSA by offering the smallest key size and the highest strength per bit and efficient computation. Internet standards such as Secure Socket Layer (SSL), IP security (IPsec), and Pretty Good Privacy (PGP) rely on public-key cryptosystems for key management.
The mathematical simplicity of RSA and the Diffie-Hellman key exchange allows for a straightforward implementation of the underlying arithmetic operations. Implementations are available in various cryptographic libraries. Arithmetically, RSA and the Diffie-Hellman key exchange operate on integer fields and primarily involve modular multiplication. In comparison, ECC is more complex. It is specified over both integer and binary polynomial fields and involves modular division in addition to modular multiplication. Implementing ECC is further complicated by algorithmic choices. Algorithms may be chosen according to the characteristics of the system architecture and constraints such as processor speed, data path width or memory size.
Different fields can underlie elliptic curves, including integer fields GF(p) and binary polynomial fields GF(2m), which are well suited for cryptographic applications. In particular, binary polynomial fields allow for fast computation in software as well as in hardware.
To make ECC commercially viable, its integration into secure protocols needs to be standardized. As an emerging alternative to RSA, the US government has adopted ECC for the Elliptic Curve Digital Signature Algorithm (ECDSA) and recommended a set of named curves over binary polynomial fields for key sizes of 163, 233, 283, 409 and 571 bit. Additional curves for commercial use were recommended by the Standards for Efficient Cryptography Group (SECG). However, only few ECC-enabled protocols have been deployed so far. Today's dominant secure Internet protocols such as SSL and IPsec rely on RSA and the Diffie-Hellman key exchange. Although standards for the integration of ECC into secure Internet protocols have been proposed, they have not yet been finalized.
The evolving wireless and web-based environment has millions of client devices including portable and desktop computers, cell phones, PDAs and SmartCards connecting to servers over secure connections. The aggregation of connections and transactions requested by client devices leads to high computational demand on the server side. Small key sizes and computational efficiency of both public and private key operations make ECC attractive to both server systems that need to process large numbers of secure connections and client devices which may have limited processing capabilities. While small key sizes and computational efficiency of both public and private key operations allow secure protocols based on ECC standards to be handled in software on the client side, the aggregation of secure connections demands high computational power on the server side that easily exceeds the capabilities of a general-purpose CPU.
While optimized implementations for specific named curves and field degrees can provide high performance, it is a desired security feature for server-side implementations to provide both ECC software libraries and hardware accelerators that support generic elliptic curves over a wide range of binary polynomial fields GF(2m). Support for generic curves on the server side is desirable since clients might choose different key sizes and curves depending on vendor preferences, security requirements and processor capabilities. Also, different types of transactions may require different security levels. In addition, the implementer of an ECC library or hardware platform may not know all curves that will eventually be used. Vendors may change their selection of curves according to security considerations, computational efficiency, market conditions and corporate policies. For hardware implementations in ASIC technology, that may result in architectural changes and costly redesigns. Also, there may be a need to support curves that are infrequently used and do not call for optimized performance.
One aspect of arithmetic operations on elliptic curves is reduction. It would be desirable to provide improved reduction capabilities to better support processing of elliptic curves.